package 剑指Offer专项突破;

/**
 * @Author zhang lei
 * @Date 2022-04-22 16:31
 */
public class Algo039 {
    /**
     * 直方图最大矩形面积
     * @param heights
     */
    public static int largestRectangleArea(int[] heights) {
        //暴力法，O(n^2)
        int maxArea = -1;
        for (int i = 0; i < heights.length; i++) {
            int height = heights[i];
            for (int j = i; j < heights.length; j++) {
                height = Math.min(height, heights[j]);
                int width = j-i+1;
                maxArea = Math.max(maxArea, height*width);
            }
        }
        return maxArea;
    }

    /**
     * 和大于等于 target 的最短子数组  008
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLen(int target, int[] nums) {
        if(nums.length == 0) {
            return 0;
        }
        int left = 0;
        int right = 0;
        int sum = nums[0];
        int length = Integer.MAX_VALUE;
        while (left<=right && right<nums.length) {
            if(sum >= target) {
                length =  Math.min(length, right-left+1);
                sum -= nums[left];
                left++;
            }else {
                right++;
                if(right<nums.length) {
                    sum += nums[right];
                }
            }
        }
        return length == Integer.MAX_VALUE? 0:length;
    }

    /**
     * 009 成绩小于k的子数组的个数
     * @param nums
     * @param k
     * @return
     */
    public static int numSubarrayProductLessThanK(int[] nums, int k) {
        int result = 0 ;
        for (int i = 0; i < nums.length; i++) {
            int cur = 1;
            for (int j = 1; j < nums.length - i+1; j++) {
                cur *= nums[j+i-1];
                if(cur < k) {
                    result++;
                }else {
                    break;
                }
            }
        }
        return result;
    }

    /**
     * 滑动窗口法
     * @param nums
     * @param k
     * @return
     */
    public static int numSubarrayProductLessThanK2(int[] nums, int k) {
        int left = 0;
        int right = 0;
        int ans = 0;
        int sum = 1;
        while(right < nums.length){
            sum *= nums[right];
            while(left <= right && sum >= k){
                sum /= nums[left];
                left++;
            }
            if(left <= right){
                ans += right - left + 1;
            }
            right++;
        }
        return ans;
    }


    public static void main(String[] args) {
        int[] arr = new int[]{10,5,2,6};
        System.out.println(numSubarrayProductLessThanK(arr, 100));
    }
}
